#include <iostream>
#include <stack>
using namespace std;

//无头结点的单链表
typedef struct ListNode
{
    ListNode(const int data)
    : mdata(data)
    , pNext(nullptr){}

    int mdata;
    ListNode *pNext;
}ListNode;

void InitListNode(ListNode **pHead)
{
    *pHead = nullptr;
}

void PushBack(ListNode **pHead, int data)
{
    ListNode *pNewNode = new ListNode(data);
    if (*pHead == nullptr)
    {
        *pHead = pNewNode;
    }
    else
    {
        ListNode *pNode = *pHead;
        while (pNode->pNext != nullptr)
        {
            pNode = pNode->pNext;
        }
        pNode->pNext = pNewNode;
    }
}

void CreateList1(ListNode **pHead)
{
    PushBack(pHead,1);
    PushBack(pHead,2);
    PushBack(pHead,3);
    PushBack(pHead,4);
    PushBack(pHead,5);
    PushBack(pHead,6);
    PushBack(pHead,7);
}

void CreateList2(ListNode **pHead)
{
    PushBack(pHead,2);
    PushBack(pHead,10);
    PushBack(pHead,8);
    PushBack(pHead,7);
    PushBack(pHead,50);
    PushBack(pHead,22);
}

void CreateList3(ListNode **pHead)
{
    PushBack(pHead,1);
    PushBack(pHead,2);
    PushBack(pHead,3);
    PushBack(pHead,4);
    PushBack(pHead,5);
    PushBack(pHead,6);
    PushBack(pHead,7);
    PushBack(pHead,8);
    PushBack(pHead,9);
    PushBack(pHead,10);
    PushBack(pHead,11);
}

//正序打印链表
void PrintListNode(ListNode *pHead)
{
    ListNode *pCur = pHead;
    while(pCur != nullptr)
    {
        cout<<pCur->mdata<<"  ";
        pCur = pCur->pNext;
    }
    cout<<endl;
}

//1.利用stack逆序打印单链表
void ReversePrintList(ListNode *pHead)
{
    cout<<"利用栈逆序打印链表：";

    stack<ListNode*> st;
    ListNode *pNode = pHead;

    while(pNode != nullptr)
    {
        st.push(pNode);
        pNode = pNode->pNext;
    }

    while(!st.empty())
    {
        cout<<st.top()->mdata<<"  ";
        st.pop();
    }
    cout<<endl;
}

//2.递归逆序打印链表
void RecursivePrintList(ListNode *pHead)
{
    if(pHead != nullptr)
    {
        RecursivePrintList(pHead->pNext);
        cout<<pHead->mdata<<"  ";
    }
}

//3.逆置反转链表
void ReverseList(ListNode *&pHead)//没有&的结果是 1
{
    cout<<"逆置反转链表：";
    if(pHead == nullptr || pHead->pNext == nullptr) return;

    ListNode *pCurNode = pHead;

    ListNode *pNewHead = nullptr;
    ListNode *pNextNode = nullptr;

    //链表中p指向某个结点代表p指向了该结点及该结点之后的那一截链表
    //新的头结点始终保持在最前面
    while(pCurNode != nullptr)
    {
        pNextNode = pCurNode->pNext;//pNextNode指向当前结点的下一个结点(包括之后的所有结点)
        pCurNode->pNext = pNewHead;//反转操作:当前结点的下一个结点指向新的头结点
        pNewHead = pCurNode;//新的头结点指向当前结点:新头结点往前移
        pCurNode = pNextNode;//当前结点指向下一个结点:当前结点指针后移
    }
    pHead->pNext = nullptr;//原头结点的next域变为空
    pHead = pNewHead;//头结点指向逆置后的结点
}

//4.合并两个有序列表，合并后依然有序
ListNode* MergeSortList(ListNode *pHead1, ListNode *pHead2)
{
    if(pHead1 == nullptr) return pHead2;
    if(pHead2 == nullptr) return pHead1;

	ListNode* pNewHead = nullptr;
    ListNode* pTail = nullptr;

	ListNode* pCur1 = pHead1;
	ListNode* pCur2 = pHead2;
	
	if (pCur1->mdata < pCur2->mdata)
	{
        pNewHead =pTail= pCur1;
		pCur1 = pCur1->pNext;
	}
	else
	{
		pNewHead =pTail= pCur2;
		pCur2 = pCur2->pNext;
	}

	while (pCur1!=nullptr && pCur2!=nullptr)
	{
		if (pCur1->mdata < pCur2->mdata)
		{
			pTail->pNext = pCur1;
			pCur1 = pCur1->pNext;
			pTail = pTail->pNext;	
		}
		else
		{
            pTail->pNext = pCur2;
			pCur2 = pCur2->pNext;
			pTail = pTail->pNext;
		}
	}

	if (nullptr == pCur1)
		pTail->pNext = pCur2;
	if (nullptr == pCur2)
		pTail->pNext = pCur1;

	return pNewHead;
}

//5.递归合并两条有序链表
ListNode* RecursiveMergeList(ListNode *pHead1, ListNode *pHead2)
{
	if (pHead1 == nullptr || pHead2 == nullptr)
		return (nullptr == pHead1) ? pHead2 : pHead1;

	ListNode *pCur1 = pHead1;
	ListNode *pCur2 = pHead2;
    ListNode *pNewHead = nullptr;

	if (pCur1->mdata < pCur2->mdata)
	{
		pNewHead = pCur1;
		pNewHead->pNext = RecursiveMergeList(pCur1->pNext, pCur2);
	}
	else
	{
        pNewHead = pCur2;
		pNewHead->pNext = RecursiveMergeList(pCur1, pCur2->pNext);
	}

	return pNewHead;
}

//6.双指针法(快慢指针法)查找链表中间结点
//查找单链表的中间节点，要求只能遍历一次链表.
//定义两个指针，一个快指针一次走两步，一个慢指针一次走一步，当快指针走到尾部，慢指针则刚好走到链表中间.
//如果链表是奇数个结点，刚好返回中间的结点；如果链表是偶数个结点，返回的是中间靠右的结点.
//如果要返回偶数结点的左边的那个，则需要加个判断链表结点个数是偶数还是奇数的条件.

ListNode* FindMiddleNode(ListNode *pHead)
{
    if(pHead == nullptr) return nullptr;
    ListNode *pFast = pHead;
    ListNode *pSlow = pHead;

    while(pFast!=nullptr &&pFast->pNext!=nullptr)
    {
        pFast = pFast->pNext->pNext;
        pSlow = pSlow->pNext;
    }

    return pSlow;
}

//7.双指针法(快慢指针法)查找链表倒数第K个结点
ListNode* FindLastKNode(ListNode *pHead, size_t k)
{
    if(pHead == nullptr || k == 0) return nullptr;

    ListNode *pFast=pHead;
    ListNode *pSlow=pHead;

    while(--k)
    {
        if(pFast == nullptr) return nullptr;
        pFast=pFast->pNext;
    }

    while(pFast!=nullptr && pFast->pNext!=nullptr)
    {
        pFast=pFast->pNext;
        pSlow=pSlow->pNext;
    }
    return pSlow;
}

//8.构造环形链表-首尾相连
void CreateCircleList(ListNode *&pList)
{
    ListNode *pNode = pList;
    while (pNode->pNext != nullptr)
    {
        pNode = pNode->pNext;
        // if (pNode->pNext == nullptr)
        // {
        //     pNode->pNext = pL1->pNext->pNext->pNext;//半环形
        //     break;
        // }
    }

    pNode->pNext=pList;//○
}

//9.双指针法(快慢指针法)判断链表是否带环
//若带环，快慢指针肯定会在环上相遇，且慢指针还没走完一整个环的路程之前，两指针已经相遇。
ListNode* HasCircle(ListNode *pHead)
{
    if(pHead == nullptr) return nullptr;

    ListNode *pFast=pHead;
    ListNode *pSlow=pHead;

    while(pFast!=nullptr && pFast->pNext!=nullptr)
    {
        pFast=pFast->pNext->pNext;
        pSlow=pSlow->pNext;

        if(pFast == pSlow)
        {
            return pSlow;
        }
    }

    return nullptr;
}

//10.求环的长度
size_t GetCircleListLength(ListNode *pHead)
{
    ListNode *pMeet = HasCircle(pHead);
    if(pHead==nullptr || pMeet==nullptr) return 0;

    ListNode *pNode = pMeet;
    size_t nCount = 1;//为什么从1开始计数？

    //遍历是从环的下一个结点开始遍历的所以相遇点要加上
    while(pNode->pNext != pMeet)
    {
        ++nCount;
        pNode=pNode->pNext;
    }
    return nCount;
}

//11.求环的入口：相遇的第一个点为环入口点
//有可能环并不是一个完整的圆周，也可能是显示一段直线链表然后形成环
//即环入口在链表中间部位。
ListNode* GetCircleListEntry(ListNode *pHead)
{
    ListNode *pMeet = HasCircle(pHead);
    if(pHead==nullptr || pMeet==nullptr) return nullptr;

    ListNode *pNode = pMeet;

    while(pNode != pMeet)
    {
        pMeet=pMeet->pNext;
        pNode=pNode->pNext;
    }
    return pMeet;
}

//12.判断两个链表是否相交
//两链表相交并不像两条直线那样相交有交点就是相交了
//两个单链表有共同的节点，那么从第一个共同节点开始，后面的节点都会重叠，直到链表结束。 
//两个链表中有一个共同结点，则这个结点里的指针域指向的下一个结点地址一样，
//所以下一个结点也会相交，所以，若相交，则两个链表呈Y或V形，最后元素必定相等。

bool IsListCrossing(ListNode *pL1, ListNode *pL2)
{
    if(pL1==nullptr || pL2==nullptr) return false;

    ListNode *pH1=pL1;
    ListNode *pH2=pL2;
    while(pH1->pNext!=nullptr)
    {
        pH1=pH1->pNext;
    }

    while(pH2->pNext!=nullptr)
    {
        pH2=pH2->pNext;
    }
    if(pH1==pH2) return true;//判断最后是否是同一结点

    return false;
}

//13.创建相交链表
void CreateCrossingList(ListNode *&pL1, ListNode *&pL2)
{
    if(pL1==nullptr || pL2==nullptr) return;

    ListNode *pH1=pL1;
    ListNode *pH2=pL2;

    ListNode *pL3=nullptr;
    CreateList3(&pL3);

    while(pH1->pNext!=nullptr)
    {
        pH1=pH1->pNext;
    }
    while(pH2->pNext!=nullptr)
    {
        pH2=pH2->pNext;
    }

    pH1->pNext=pL3;
    pH2->pNext=pL3;
}

//14.求链表交点
ListNode* GetListCrossNode(ListNode *pHead1,ListNode *pHead2)
{
    //1.构环求入口
    // CreateCircleList(pL1);
    // return HasCircle(pL2);

    //2.构环求入口
	// ListNode *pCur1 = pL1;
	// ListNode *pCur2 = pL2;
	// while (pCur1->pNext != nullptr)
	// {
	// 	pCur1 = pCur1->pNext;
	// }
	// pCur1->pNext = pCur2;
	// return GetCircleListEntry(pL1);

    //3.根据长度差求交点
	ListNode * pCur1 = pHead1;
	ListNode * pCur2 = pHead2;
	size_t count1 = 0;
	size_t count2 = 0;
	//求长度差
	ListNode * tmp1 = pCur1;
	ListNode * tmp2 = pCur2;
	while (tmp1)
	{
		tmp1 = tmp1->pNext;
		count1++;
	}
	while (tmp2)
	{
		tmp2 = tmp2->pNext;
		count2++;
	}
	int count = count2 - count1;
	//求交点
	if (count > 0)                      //2比1长
	{
		while (count--)
		{
			pCur2 = pCur2->pNext;
		}
	}
	else                                //1比2长
	{
		while (count++)
		{
			pCur1 = pCur1->pNext;
		}
	}
	while (pCur1 != pCur2)
	{
		pCur1 = pCur1->pNext;
		pCur2 = pCur2->pNext;
	}
	return pCur1;
}

//15.删除一个无头结点单链表的非尾结点（不能遍历链表）
void DelNotTail(ListNode *pos)
{
	ListNode *pNode = pos->pNext;
	pos->mdata = pNode->mdata;
	pos->pNext = pNode->pNext;
	delete pNode;
	pNode = nullptr;
}

//16.在无头结点单链表的一个非头节点前插入一个结点
//可以插到此节点后面，再交换两个节点的内容
void InsertNode(ListNode *pos, int data)
{
	ListNode * pNewNode = new ListNode(pos->mdata);
	pNewNode->pNext = pos->pNext;
	pos->pNext = pNewNode;
	pos->mdata = data;
}

//17.单链表实现约瑟夫环(JosephCircle) 
//解释一下约瑟夫环，它是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。
//从编号为1的人开始报数，数到k的那个人出列；他的下一个人又从1开始报数，数到k的那个人又出列；依此规律重复下去，直到圆桌周围的人只剩下一个人。
//我们要先把链表构成环，再确定删除点。
ListNode* JosephCircle(ListNode *&pHead,int M)
{
// 	ListNode *pCur = pHead;                 //构环
// 	while (pCur->pNext != nullptr)
// 	{
// 		pCur = pCur->pNext;
// 	}
// 	pCur->pNext = pHead;

    CreateCircleList(pHead);//构环

	ListNode *pcur = pHead;
	while (pcur->pNext == pcur)
	{
		while (--M)
		{
			pcur = pcur->pNext;
		}

		//删除节点
		ListNode *pdel = pcur->pNext;
		pcur->pNext = pdel->pNext;
		pcur->mdata = pdel->mdata;
		delete pdel;
		pdel = nullptr;
	}
	pcur->pNext = nullptr;
	pcur = pHead;

	return pcur;
}

//18.单链表排序--冒泡排序
void BubbleSort(ListNode * pHead)
{
	if (pHead==nullptr || pHead->pNext==nullptr)
		return;
	ListNode * pCur = pHead;
	ListNode * Tail = nullptr;
	ListNode * pNextNode = nullptr;
	while (pCur->pNext != Tail)
	{
		while (pCur->pNext != Tail)
		{
			pNextNode = pCur->pNext;
			if (pCur->mdata > pNextNode->mdata)
				swap(pCur->mdata, pNextNode->mdata);
			pCur = pCur->pNext;
		}
		Tail = pCur;
		pCur = pHead;
	}
}

int main()
{
    ListNode *pL1, *pL2, *pL3;

    InitListNode(&pL1);
    InitListNode(&pL2);
    InitListNode(&pL3);

    CreateList1(&pL1);
    CreateList2(&pL2);
    CreateList3(&pL3);

    cout<<"最后赢家："<<JosephCircle(pL3,7)->mdata<<endl;


    // CreateCircleList(pL1);
    // CreateCrossingList(pL1,pL2);

    // cout<<"打印链表：";
    // PrintListNode(pL1);
    // PrintListNode(pL2);
    // BubbleSort(pL1);
    // PrintListNode(pL1);
    // BubbleSort(pL2);
    // PrintListNode(pL2);
    // ListNode *pMergeList = MergeSortList(pL1,pL2);
    // PrintListNode(MergeSortList(pL1,pL2));
    // PrintListNode(RecursiveMergeList(pL1,pL2));

    // if(IsListCrossing(pL1,pL2)) cout<<"相交"<<endl;
    // else cout<<"不相交"<<endl;
    // cout<<"链表交点："<<GetListCrossNode(pL1,pL2)->mdata<<endl;

    // ReversePrintList(pL1);
    // cout<<"递归打印链表：";
    // RecursivePrintList(pL1);
    // cout<<endl;
    // ReverseList(pL1);
    // PrintListNode(pL1);

    // cout<<"查找链表的中间结点："<<FindMiddleNode(pL1)->mdata<<endl;
    // ListNode *pLKNode = FindLastKNode(pL1,2);
    // if(pLKNode == nullptr) cout<<"超出链表长度!"<<endl;
    // else cout<<"查找链表倒数第K个结点："<<pLKNode->mdata<<endl;

    // ListNode *pNode = HasCircle(pL1);
    // if(pNode == nullptr) cout<<"无环"<<endl;
    // else cout<<"有环--环长度为："<<GetCircleListLength(pL1)<<endl;
    // cout<<"环的入口为："<<pNode->mdata<<endl;
    // cout<<"环的入口为："<<GetCircleListEntry(pL1)->mdata<<endl;

    return 0;
}